﻿/**
 * Copyright (C) 2011 original author and authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NGuice.Inject.Internal.Util
{
    /// <summary>
    /// 基于哈希的集合算法
    /// </summary>
    static class Hashing
    {
        /*
   * This method was written by Doug Lea with assistance from members of JCP
   * JSR-166 Expert Group and released to the public domain, as explained at
   * http://creativecommons.org/licenses/publicdomain
   */
        internal static int Smear(int hashCode)
        {
            uint uhashCode = (uint)hashCode;
            uhashCode ^= (uhashCode >> 20) ^ (uhashCode >> 12);
            return (int)(uhashCode ^ (uhashCode >> 7) ^ (uhashCode >> 4));
        }

        // We use power-of-2 tables, and this is the highest int that's a power of 2
        private static readonly int MAX_TABLE_SIZE = 1 << 30;

        // If the set has this many elements, it will "max out" the table size
        private static readonly int CUTOFF = 1 << 29;

        private static int HighestOneBit(int i)
        {
            i |= (i >> 1);
            i |= (i >> 2);
            i |= (i >> 4);
            i |= (i >> 8);
            i |= (i >> 16);
            return (int)(i - RightMove(i, 1));
        }

        // Size the table to be at most 50% full, if possible
        internal static int ChooseTableSize(int setSize)
        {
            if (setSize < CUTOFF)
            {
                return HighestOneBit(setSize) << 2;
            }
            // The table can't be completely full or we'll get infinite reprobes
            Preconditions.CheckArgument(setSize < MAX_TABLE_SIZE, "collection too large");
            return MAX_TABLE_SIZE;
        }

        /// <summary>
        /// 无符号右移
        /// </summary>
        /// <param name="value"></param>
        /// <param name="pos"></param>
        /// <returns></returns>
        public static int RightMove(int value, int pos)
        {
             if (pos != 0) //移动 0 位时直接返回原值
            {
                int mask = 0x7fffffff; // int.MaxValue = 0x7FFFFFFF 整数最大值
                value >>= 1; //第一次做右移，把符号也算上，无符号整数最高位不表示正负但操作数还是有符号的，有符号数右移1位，正数时高位补0，负数时高位补1
                value &= mask; //和整数最大值进行逻辑与运算，运算后的结果为忽略表示正负值的最高位
                value >>= pos-1; //逻辑运算后的值无符号，对无符号的值直接做右移运算，计算剩下的位
            }
            return value;
        }
    }
}
